package com.hspedu.newData.dmsxl.树.构造二叉树;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-13 
 * @Version: 1.0
 */

public class LCR124推理二叉树 {

    Map<Integer,Integer> map = new HashMap<>();

    public TreeNode deduceTree(int[] preorder, int[] inorder) {

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return find(preorder,0, preorder.length, inorder,0, inorder.length);

    }

    public TreeNode find(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){

        if (preBegin>=preEnd && inBegin>=inEnd){
            return null;
        }

        int i = map.get(preorder[preBegin]);

        TreeNode root = new TreeNode(inorder[i]);
        int len = i - preBegin;
        root.left = find(preorder,preBegin+1, preBegin + 1 + len,inorder,inBegin,i);
        root.right = find(preorder,preBegin+1+len, preEnd,inorder,i+1,inEnd);

        return root;
    }
}
